﻿#include<iostream>
#include<map>
#include<vector>
#include<list>
#include<queue>
#include<algorithm>
#include<stdio.h>
using namespace std;

const int MAXVERTICES= 50 ;   //最大顶点数n
const int MAXEdgeS= 50 ;   //最大边数

typedef struct
{
	int   v1;
	int   v2;
}EDGE_STRU;		//保存边的顶点

class Graph{
public:
	Graph();
	~Graph();

	bool  InsertEdge(int v1, int v2,int edgeno);   //插入一条边,名称为edgeno
	bool  DeleteEdge(int v1, int v2,int edgeno);   //删除一条边,名称为edgeno

	bool  InsertVertex(int v);   //插入一个顶点（和任何顶点不邻接）,名称为v
	bool  DeleteVertex(int v);  //删除与顶点V关联的所有边

	map<int, EDGE_STRU > edge_map;      //key:边的标识，value：边所对应的顶点

	bool MatrixA[MAXVERTICES][MAXEdgeS];			//关联矩阵
	bool MatrixX[MAXVERTICES][MAXVERTICES];		//邻接矩阵
	bool MatrixQ[MAXVERTICES][MAXVERTICES];	    //全连通矩阵


//protected:
//	int   numedge;    		//图的边数
//	int   numVertices ;		//图的顶点数
	list<int>  vertex ;  	   //图的顶点集合
	void printMatrixA();         //打印关联矩阵
	void printMatrixX();         //打印邻接矩阵
	void printMatrixQ();         //打印全连通矩阵
	void GenMatrixA();           //生成关联矩阵
	void GenMatrixX();           //生成邻接矩阵
	void GenMatrixQ();           //生成全连通矩阵
	bool MatrixT[MAXVERTICES][MAXVERTICES];   //临时

private:
	bool flag1;                  //flag1作为图形结构改变的标志位，flag改变则表明图形变化
	bool flag2;                  //flag2作为顶点顺序改变的标志
	bool flag3;                  //判断是否有新的关联矩阵产生,重新生成邻接矩阵后置为0
	vector<int> vertex_list;     //根据顶点表vertex的各元素顺序将各元素存在vector中实现随机访问


};

//函数实现
Graph::Graph(){
	flag1 = true;
	flag2 = false;
	flag3 = true;
	vertex_list.clear();
}

Graph::~Graph(){
}

//插入一条边
bool Graph::InsertEdge(int v1, int v2,int edgeno){
	EDGE_STRU edge = {v1, v2};
	edge_map.insert(map<int, EDGE_STRU>::value_type(edgeno,edge));
	flag1=true;//待处理
	return 0;
}

//删除一条边
bool Graph::DeleteEdge(int v1, int v2,int edgeno){
	edge_map.erase(edgeno);
	flag1=true;//待处理
	return 0;
}

//插入一个顶点
bool Graph::InsertVertex(int v){
	vertex.push_back(v);
	flag2=false;//顶点顺序改变
	flag1=true;//模型改变
	return 0;
}

//删除顶点v及与其相关的边
bool Graph::DeleteVertex(int v){
	for(map<int,EDGE_STRU>::iterator iter=edge_map.begin();iter!=edge_map.end();iter++){
		if((iter->second.v1==v)||(iter->second.v2==v)){
			edge_map.erase(iter--);
		}
	}
	vertex.remove(v);//在顶点表里删除顶点v
	flag2=false;
	flag1=true;
	return 0;
}

//生成关联矩阵
void Graph::GenMatrixA(){
	if(flag1){	//判断模型是否改变
		if(!flag2){	//判断顶点顺序是否改变
			vertex.sort();//将顶点升序排列
			flag2=true;
		}

		int i,j;
		//将关联矩阵元素置为0
		for (i = 0; i < MAXVERTICES; i++ ) {
			for (j = 0; j < MAXEdgeS; j++ ) {
				MatrixA[i][j] = 0;
			}
		}
		//重新生成关联矩阵
		j = 0;
		for (map<int, EDGE_STRU>::iterator iter = edge_map.begin(); iter != edge_map.end(); iter++) {
			i = 0;
			for (list<int>::iterator it1 = vertex.begin(); it1 != vertex.end(); it1++) {
				if (*it1 == iter->second.v1) {
					MatrixA[i][j] = 1;
					break;
				}
			i++;
			}
			i = 0;
			for (list<int>::iterator it2 = vertex.begin(); it2 != vertex.end(); it2++) {
				if (*it2 == iter->second.v2) {
					MatrixA[i][j] = 1;
					break;
				}
			i++;
			}
			j++;
		}
		flag1=false;
		flag3=true;
	}
}

//生成邻接矩阵
void Graph::GenMatrixX(){
	//先生成关联矩阵，判断模型有没有改变
	GenMatrixA();
	if(flag3){
		//将邻接矩阵元素置成0
		for (int i = 0; i < MAXVERTICES; i++ ) {
			for (int j = 0; j < MAXVERTICES; j++ ) {
				MatrixX[i][j] = 0;
			}
		}
		//根据关联矩阵生成邻接矩阵
		for (int j = 0; j < edge_map.size(); j++ ){
			bool fg=false;//是否找到该列第一个非零值
			int temp_row;
			for (int i = 0; i < vertex.size(); i++ ){
				if (MatrixA[i][j] == 1) {
					if (!fg) {
						temp_row = i;
						fg = true;
				}
				else{
					MatrixX[temp_row][i] = 1;
					MatrixX[i][temp_row] = 1;
					break;
				}
			}
		}
		flag3=false;
		 }
	}
}

//生成全连通矩阵
void Graph::GenMatrixQ(){
	GenMatrixX();
	//初始化
	for (int i = 0; i < vertex.size(); i++){
		for (int j = 0; j < vertex.size(); j++){
			if (i == j)
				MatrixQ[i][j] = 1;
			else
				MatrixQ[i][j] = 0;
		}
	}
	for (int n = 0; n < vertex.size() - 1; n++){
		for (int i = 0; i < vertex.size(); i++){
			for (int j = 0; j < vertex.size(); j++){
				MatrixT[i][j] = MatrixQ[i][j];
			}
		}
		for (int i = 0; i < vertex.size(); i++){
			for (int j = 0; j < vertex.size(); j++){
				for (int k = 0; k < vertex.size(); k++) {
					MatrixQ[i][j] =  MatrixT[i][j] || (MatrixT[i][k]&& MatrixX[k][j]);
					if (MatrixQ[i][j] )
						break;
				}
			}
		}
	}
}

//打印关联矩阵
void Graph::printMatrixA(){
		GenMatrixA();
		cout<<"输出关联矩阵为:"<<endl;
		//输出邻接矩阵的列对应的边
		for (map<int, EDGE_STRU>::iterator iter = edge_map.begin();iter != edge_map.end();iter++) {
			cout<<'\t'<<"("<<iter->first<< ")";
		}
		cout<<endl;
		cout<<"----------关联矩阵-----------"<<endl;
		vertex_list.assign(vertex.begin(),vertex.end());//将vertex的元素复制到vertex_list中
		for (int i = 0; i < vertex.size(); i++) {
			cout<<vertex_list[i]<<"|"<<'\t';
			for (int j = 0; j < edge_map.size(); j++) {
				cout<<MatrixA[i][j]<<'\t';
			}
		cout<<endl;
		}
}

//打印邻接矩阵
void Graph::printMatrixX(){
	GenMatrixX();
	vertex_list.assign(vertex.begin(),vertex.end());//将vertex的元素复制到vertex_list中
	cout<<"输出邻接矩阵为:"<<endl;
	//输出邻接矩阵列对应的顶点
	for (int i= 0; i< vertex.size(); i++){
		cout <<'\t'<<vertex_list[i];
	}
	cout<<endl;
	cout<<"--------邻接矩阵------------"<<endl;
	for (int i = 0; i < vertex.size(); i++) {
		cout<<vertex_list[i]<<"|"<<'\t';
		for (int j = 0; j < edge_map.size(); j++) {
			cout<<MatrixX[i][j]<<'\t';
		}
	cout<<endl;
	}
}

//打印全连通矩阵
void Graph::printMatrixQ(){
	GenMatrixQ();
	vertex_list.assign(vertex.begin(),vertex.end());//将vertex的元素复制到vertex_list中
	cout<<"输出全连通矩阵:"<<endl;
	for (int i= 0; i< vertex.size(); i++){
		cout <<'\t'<<vertex_list[i];
	}
	cout<<endl;
	cout<<"------------全连通矩阵---------"<<endl;
	for (int i = 0; i < vertex.size(); i++) {
		cout<<vertex_list[i]<<"|"<<'\t';
		for (int j = 0; j < edge_map.size(); j++) {
			cout<<MatrixQ[i][j]<<'\t';
		}
	cout<<endl;
	}
}

class Search{
public:
  Search(){};
  ~Search(){};

  void DFS_init(bool graph_adjm[MAXVERTICES][MAXVERTICES],list<int> vertexlist,int nd_no);  //DFS初始化程序，graph为邻接矩阵，vertexlist为顶点表，nd_no为搜索的起点
  void BFS_init(bool graph_adjm[MAXVERTICES][MAXVERTICES],list<int> vertexlist,int nd_no);   //BFS初始化程序，graph为邻接矩阵，vertexlist为顶点表，nd_no为搜索的起点

  vector<int>  vertex_flag;     //顶点访问标志
  void DFS_main(bool graph_adjm[MAXVERTICES][MAXVERTICES], int i);  //DPF迭代
  void BFS_main(bool graph_adjm[MAXVERTICES][MAXVERTICES], int i);  //BFS
	
private: 
  vector<int> vertex_stack;  
  vector<int> vertex_list;     //根据list的各元素顺序将各元素存在vector中，实现随机访问
  queue<int>  vertex_order;    //BFS时，访问过的节点，FIFO
  vector<int > m_v_visit_order; //按照访问节点的顺序保存节点
};

//DFS初始化程序，graph为邻接矩阵，vertex_list为顶点表，nd_no为搜索的起点，新起点表示不同连通子图的起点
void Search::DFS_init(bool graph_adjm[MAXVERTICES][MAXVERTICES],list<int> vertexlist,int nd_no){
	vertex_list.assign(vertexlist.begin(),vertexlist.end());     //将vertexlist的元素复制到vertex_list中，实现随机访问
	vertex_flag.assign(vertex_list.size(),0);                      //初始化顶点表访问标志位，0表示未访问
	vector<int>::iterator iter=find(vertex_list.begin(),vertex_list.end(),nd_no);
	int i_start=iter-vertex_list.begin();

	cout<<"DFS起始节点:"<<vertex_list[i_start]<<endl;

	//根据起始顶点，遍历
	for(int i=i_start;i<vertex_list.size();i++){
		if(vertex_flag[i]==0){
			cout<<endl<<"新起点:"<<vertex_list[i]<<endl;
			m_v_visit_order.clear();        //新的连通子图
			DFS_main(graph_adjm,i);
			cout<<"DFS访问顺序为:";
			for(vector<int>::iterator iter=m_v_visit_order.begin();iter!=m_v_visit_order.end();iter++){
				cout<<*iter<<"	";
			}
		}
	}
	for(int i=0;i<i_start;i++){
		if(vertex_flag[i] == 0){
			cout<<endl<<"新起点:"<< vertex_list[i]<<endl;
			m_v_visit_order.clear();        //新的连通子图
			DFS_main(graph_adjm,i);
			cout<<"DFS访问顺序为:";
			for(vector<int >::iterator iter=m_v_visit_order.begin();iter!= m_v_visit_order.end();iter++){
				cout<<*iter<<"	";
			}
		}
	}
}

//BFS初始化程序，graph为邻接矩阵，vertex_list为顶点表，nd_no为搜索的起点
void Search::BFS_init(bool graph_adjm[MAXVERTICES][MAXVERTICES],list<int> vertexlist, int nd_no){
    vertex_list.assign(vertexlist.begin(), vertexlist.end() );     //将vertex_list的元素复制到_vertex_list中，实现随机访问
    vertex_flag.assign(vertex_list.size(), 0);    //初始化顶点表访问标志位，0表示未访问
    vector<int>::iterator iter = find(vertex_list.begin(), vertex_list.end(), nd_no); //待补充，错误处理
  int i_start = iter - vertex_list.begin();

  cout << "BFS起始节点:" <<vertex_list[i_start] << endl;

  //根据起始顶点，遍历
  for (int i= i_start; i < vertex_list.size(); i++ ){
    if (vertex_flag[i] == 0) {
      //_vertex_order.push(_vertex_list[i] );   //将该节点入栈
      vertex_flag[i] = 1;
      cout  << endl <<"新起点：" << vertex_list[i] << endl;
      BFS_main(graph_adjm, i);
    }
  }
  for (int i = 0; i < i_start; ){
    if (vertex_flag[i] == 0) {
      cout << endl << "新起点：" << vertex_list[i] << endl;
      DFS_main(graph_adjm, i);
    }
  }

}

//DFS迭代主程序，i 表示第i个顶点
void Search::DFS_main(bool graph_adjm[MAXVERTICES][MAXVERTICES], int i){
  vertex_stack.push_back(vertex_list[i] );   //将该节点入栈
  vertex_flag[i] = 1;
  cout << vertex_list[i] << "    ";                     //打印访问的节点
  m_v_visit_order.push_back(vertex_list[i]);
  for (int j = 0; j < vertex_list.size(); j++ ) {
    if (graph_adjm[i][j] != 0 && vertex_flag[j] == 0){
      //如果关联矩阵的第(i-1)行和第(j-1)行所表示节点邻接，且第(j-1)列所表示的节点未访问则执行此步
      DFS_main(graph_adjm, j);
    }
  }

}

//BFS,i 表示第i个顶点,NEW:表示从该点进行BFS
void Search::BFS_main(bool graph_adjm[MAXVERTICES][MAXVERTICES], int i){
    for (int j = 0; j < vertex_list.size(); j++ ) {
    //cout << "MX[" << i << "][" << j << "] = " << graph_adjm[i][j] << "@@";
    if (graph_adjm[i][j] != 0 && vertex_flag[j] == 0){
      //如果关联矩阵的第(i-1)行和第(j-1)行所表示节点邻接，且第(j-1)列所表示的节点未访问则执行此步
      vertex_order.push(j );   //
      vertex_flag[j] = 1;
      cout << vertex_list[j] << "    ";                     //打印访问的节点
    }
  }

  if(!vertex_order.empty() ){
    int no_temp = vertex_order.front();
    vertex_order.pop();
    cout << endl << "NEW:" << vertex_list[no_temp] << endl;
    BFS_main(graph_adjm, no_temp);
  }

}

int main(){
	cout<<"this is the lecture 5!"<<endl;
	Graph 	graph;
	Search	search;

	//读取图(插入顶点）
	graph.InsertVertex(1);
	graph.InsertVertex(2);
	graph.InsertVertex(3);
	graph.InsertVertex(4);
	graph.InsertVertex(5);
	graph.InsertVertex(6);
	graph.InsertVertex(7);
	graph.InsertVertex(8);
	graph.InsertVertex(9);
	//读取图（插入边）
	graph.InsertEdge(1,6,1);
	graph.InsertEdge(1,2,2);
	graph.InsertEdge(3,6,3);
	graph.InsertEdge(7,8,4);
	graph.InsertEdge(7,9,5);
	graph.InsertEdge(6,9,6);
	graph.InsertEdge(5,8,7);
	graph.InsertEdge(4,8,8);
	graph.InsertEdge(8,9,9);
	graph.InsertEdge(1,5,10);

	cout<<"===============Question 1======================="<<endl;
	//Q1 START
	graph.printMatrixA();         //打印关联矩阵
	graph.printMatrixX();         //打印邻接矩阵
	graph.printMatrixQ();         //打印全连通矩阵
	//补充
	//Q1 END

	cout<<"===============Question 2======================="<<endl;
	//Q2 START
	search.DFS_init(graph.MatrixX, graph.vertex, 1 );
	cout << endl;
	cout<<"========DFS=========" << endl;
	search.BFS_init(graph.MatrixX, graph.vertex, 1 );
	//Q2 END

	cout <<"==============Question 3======================" << endl;

	//Q3 START
	graph.DeleteVertex(9);
	graph.DeleteEdge(1, 5, 10);
	graph.printMatrixA();         //打印关联矩阵
	graph.printMatrixX();         //打印邻接矩阵
	graph.printMatrixQ();         //打印全连通矩阵
	search.DFS_init(graph.MatrixX,graph.vertex,1 );
	cout << endl << "======DFS=======" << endl;
	search.BFS_init(graph.MatrixX, graph.vertex,1 );
//Q3 END

	cout <<"=============Question 4=======================" << endl;

//Q4 START
	graph.InsertVertex(9);
	graph.InsertEdge(6, 9, 6);
	graph.InsertEdge(7, 9, 5);
	graph.InsertEdge(8, 9, 9);
	graph.InsertEdge(1, 5, 10);
	graph.InsertEdge(2, 4, 11);
	graph.printMatrixA();         //打印关联矩阵
	graph.printMatrixX();         //打印邻接矩阵
	graph.printMatrixQ();         //打印全连通矩阵
	search.DFS_init(graph.MatrixX, graph.vertex, 1 );
	cout << endl << "=========DFS========" << endl;
	search.BFS_init(graph.MatrixX, graph.vertex, 1 );

//Q4 END
	return 0;
}
